1. Field
The present disclosure generally relates to hybrid positioning systems and more specifically, the assessment of the quality of a set of visible satellites to be used in a positioning system.
2. Description of Related Art
Positioning using radio signals has attracted increasing attention in the field of location and tracking. The initial research studies on satellite positioning systems (SPS) resulted in a very accurate Global Positioning System (GPS) which was initially used for military applications and later broadly used for commercial and personal applications. The availability of SPS-based positioning has been a major factor in the introduction of Location Based Services (LBS) in advanced mobile communication devices such as smartphones. By determining the position of the receiver, the system is able to provide more effective and more appropriate services to the user.
The Navstar Global Positioning System (GPS) operated by the US Government leverages about two-dozen orbiting satellites in medium-earth orbits as reference points. A user equipped with a GPS receiver can estimate his three-dimensional position (latitude, longitude, and altitude) anywhere at any time within several meters of the true location as long as the receiver can see enough of the sky to have four or more satellites “in view.” Cellular carriers can use signals originating from and received at cell towers to determine a user's or a mobile device's location. Assisted GPS (AGPS) is another model that combines both GPS and cellular tower techniques to estimate the locations of mobile users who may be indoors and must cope with attenuation of GPS signals on account of sky blockage. In this model, the cellular network attempts to help a GPS receiver improve its signal reception by transmitting information about the satellite positions, their clock offsets, a precise estimate of the current time, and a rough location of the user based on the location of cell towers. No distinction is made in what follows between GPS and AGPS.
All positioning systems using satellites as reference points are referred to herein as Satellite-based Positioning System (SPS). While GPS is the only operational SPS at this writing, other systems are under development or in planning A Russian system called GLONASS and a European system called Galileo may become operational in the next few years. All such systems are referred to herein as SPS. GPS, GLONASS and Galileo are all based on the same basic idea of trilateration, i.e., estimating a position on the basis of measurements of ranges to the satellites whose positions are known. In each case, the satellites transmit the values of certain parameters which allow the receiver to compute the satellite position at a specific instant. The ranges to satellites from a receiver are measured in terms of the transit times of the signals. These range measurements can contain a common bias due to the lack of synchronization between the satellite and receiver (user device) clocks, and are referred to as pseudoranges. The lack of synchronization between the satellite clock and the receiver (user device) clock can result in a difference between the receiver clock and the satellite clock, which is referred to as internal SPS receiver clock bias or receiver clock bias, here. In order to estimate a three dimensional position there is a need for four satellites to estimate receiver clock bias along with three dimensional measurements. Additional measurements from each satellite correspond to pseudorange rates in the form of Doppler frequency. References below to raw SPS measurements are intended generally to mean pseudoranges and Doppler frequency measurements. References to SPS data are intended generally to mean data broadcast by the satellites. References to an SPS equation are intended to mean a mathematical equation relating the measurements and data from a satellite to the position and velocity of an SPS receiver.
WLAN-based positioning is a technology which uses WLAN access points to determine the location of mobile users. Metro-wide WLAN-based positioning systems have been explored by several research labs. The most important research efforts in this area have been conducted by the PlaceLab (www.placelab.com, a project sponsored by Microsoft and Intel); the University of California, San Diego ActiveCampus project (ActiveCampus—Sustaining Educational Communities through Mobile Technology, technical report #CS2002-0714); and the MIT campus-wide location system. There is only one commercial metropolitan WLAN-based positioning system in the market at the time of this writing, and it is referred to herein as the WPS (WiFi positioning system) product of Skyhook Wireless, Inc (www.skyhookwireless.com).
SPS is based on triangulation (trilateration) using multiple distance measurements from multiple satellites. The receiver measures its distance from at least four satellites. Based on the distance measurements, the receiver solves a set of quadratic equations including (xr, yr, zr), coordinates of the receiver, and τr, receiver clock bias. In order to quantify the accuracy of the location estimate (quality of estimate of the reported location,) SPS systems use several metrics such as Dilution of Precision (DOP0) (Indices, like index 0, are used to differentiate different DOP definitions here). Widely used in literature, the geometry of the set of visible satellites, indicated by DOP0 metric, is assumed to have correlation with estimated location error. In other words, DOP0 relates the geometry of the satellites to the quality of the location estimate.
Different DOP0 metrics and values, such as Horizontal Dilution of Precision (HDOP) or Position Dilution of Precision (PDOP)), have been used in the last two decades to decide on the quality of a set of satellites used for positioning. A set of satellites can be considered for positioning if its resulted DOP0 metric is below a threshold. Note that DOP0 metric can be measured differently with different scales, but its importance is to provide a means to assess the quality of the set of visible satellites.
For example, if all the satellites are exactly above the location of the receiver or very close to one another that set of satellites cannot be used for positioning. Geometrically, satellites should be spread apart in the sky. The best condition is one satellite above the receiver and others evenly distributed in the sky with good visibility by the receiver. In best scenarios, if all the satellites have angle of 60 degrees to one another, that geometry of satellites can provide more accurate results for positioning. Angles of less than 30 degrees result in satellites which are either close to one another or aligned on the same line that connects them to the receiver. Very wide angles such as 150 degrees also provide satellites which are very far from one another and hence they can only be visible from the horizon with respect to a GPS receiver. Such cases provide bad geometry for satellite positioning. Satellites in the proximity of other satellites and/or satellites aligned on the same plane (i.e. forming a coplanar problem) are normally not useful in location determination as they provide redundant information about receiver. For example, two satellites which are close to one another provide the same range estimation to the receiver and hence one of range estimations can be ignored. Similarly, when satellites are aligned in such a way that the plane which passes through them also passes through the receiver location (or close by locations) the range estimation from the satellites to the receiver are not independent and become redundant. In both cases, the algorithm which solves the range estimation equations to find the receiver location will fail (or converge very slowly) as its input includes redundant data.
The term DOP0 only applies to the cases where the receiver can see four or more satellites as described below. With fewer satellites, it is mathematically impossible to obtain a DOP0 value when traditional methods are used.
The traditional method of obtaining all DOP0 metrics is to use the estimated location of receiver, (xr, yr, zr), and each of the visible satellites (four or more), (xsi, ysi, zsi), where i indicates the index of the visible satellite. The SPS system forms a geometry matrix
  G  =      [                                        Δ            ⁢                                                  ⁢                          x              1                                                            Δ            ⁢                                                  ⁢                          y              1                                                            Δ            ⁢                                                  ⁢                          z              1                                                            -            1                                                ⋮                          ⋮                          ⋮                          ⋮                                                  Δ            ⁢                                                  ⁢                          x              n                                                            Δ            ⁢                                                  ⁢                          y              n                                                            Δ            ⁢                                                  ⁢                          z              n                                                            -            1                                ]  where each Δ component can be determined as follows,
            Δ      ⁢                          ⁢              x        i              =                            x          r                -                  x                      s            i                                      R        i                        Δ      ⁢                          ⁢              y        i              =                            y          r                -                  y                      s            i                                      R        i                        Δ      ⁢                          ⁢              z        i              =                            z          r                -                  z                      s            i                                      R        i            where Ri is the estimated range between the estimated receiver location and i the satellite.
It should be noted that matrix G has dimension n×4, where n represents the number of visible satellites. The next step to determine the DOP0 values is to form another matrix H=GT×G with dimensionality of 4×4 (T represents transpose of a matrix). The inverse of matrix H, denoted by H−1, is used to determine the DOP values. The diagonal elements of H−1 are used to form Position Dilution of Precision (PDOP) and Time Dilution of Precision (TDOP). Other DOP0 values, such as HDOP or Vertical Dilution of Precision (VDOP), are computed similarly.
The mathematical representation of DOP0 values can be related to the geometry of the set of satellites. In principle, a good set of satellites for SPS is a set of satellites that are well-spread in the sky. Very close satellites or coplanar satellites provide very little information about the receiver's position. FIG. 1 illustrates a good set of satellites versus a bad set of satellites. Relating the geometry of satellites to DOP0 values, we can conclude that a good set of satellites results in smaller DOP0 values and a bad set of satellites results in large DOP0 values. Therefore, it is very instructive and significant to obtain DOP0 values for a specific set of satellites relative to an estimated receiver location. The positioning system, in our case an integrated WLAN-PS and SPS environment, can effectively decide if a set of satellites is usable for positioning or if it has a bad geometry and will produce large location error. The DOP0 value is directly related to the volume of the tetrahedron formed using each satellite as an end point of the tetrahedron (in case of four satellites) or similar shapes (in case of more than four satellites) formed by the satellites.
As can be seen from the equations, the smallest number of satellites to form an invertible H matrix is four. In SPS, fewer than four satellites results in H4×4 with dependent rows and consequently H−1 does not exist. This fact poses a problem for hybrid positioning schemes with fewer than four visible satellites. The goal is for a positioning scheme to assess the quality of a set of visible satellites. What is needed is a metric to relate the geometry of the visible satellites to quality of the set of visible satellites and to improve the quality of the estimate of the receiver's location when fewer than four satellites are present.